package E_2024;

import java.util.*;

public class E_100_1 {
    /*
    流浪地球计划在赤道上均匀部署了N个转向发动机，按位置顺序编号为0~N-1。
    1） 初始状态下所有的发动机都是未启动状态；
    2） 发动机起动的方式分为“手动启动”和“关联启动”两种方式；
    3） 如果在时刻1一个发动机被启动，下一个时刻2与之相邻的两个发动机就会被“关联启动”；
    4） 如果准备启动某个发动机时，它已经被启动了，则什么都不用做；
    5） 发动机0与发动机N-1是相邻；
    地球联合政府准备挑选某些发动机在某些时刻进行“手动启动”，当然最终所有的发动机都会被启动。
    哪些发动机最晚被启动呢？

    输入描述：
        第一行两个数字N和E，中间有空格
        N代表部署发动机的总个数，E代表计划手动启动的发动机总个数
        1<N<=1000，1<=E<=1000,E<=N
        接下来共E行，每行都是两个数字T和P，中间有空格
        T代表发动机的手动启动时刻，P代表此发动机的位置编号。
        0<=T<=N,0<=P<=N
    输出格式
        第一行一个数字N，以回车结束。N代表最后被启动的发动机个数。第二行N个数字，中间有空格，以回车结束。每个数字代表发动机的位置编号，从小到大排序。
    输入示例
    8 2
    0 0
    1 7
    输出
    1
    4
     */
    public static void main(String[] args) {
        ans2();
    }
    public static void ans1(){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int e = sc.nextInt();
        int[] is = new int[n];
        Arrays.fill(is, -1);
        for (int i = 0; i < e; i++) {
            int t = sc.nextInt();
            int p = sc.nextInt();
            int left = p;
            int right = p;
            for (int j = 0; j < n; j++) {
                if (is[left] > t || is[left] == -1)
                    is[left] = t;
                if (is[right] > t || is[right] == -1)
                    is[right] = t;
                t++;
                left = left == 0 ? n-1 : --left;
                right = right == n-1 ? 0 : ++right;
            }
        }
        System.out.println(Arrays.toString(is));
        int max = 0;
        for (int i : is) {
            max = Math.max(i,max);
        }
        int nums = 0;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < is.length; i++) {
            if (is[i] == max){
                nums++;
                ans.add(i);
            }
        }
        System.out.println(nums);
        System.out.println(ans);
    }
    public static void ans2(){
        Scanner scanner = new Scanner(System.in);
        // 读取N和E
        int N = scanner.nextInt();
        int E = scanner.nextInt();
        int[] temp = new int[N];
        Arrays.fill(temp,-1);
        // 用于记录发动机的启动时刻和位置
        Queue<Integer[]> queue = new PriorityQueue<>(Comparator.comparing(a->a[0]));
        //T代表发动机的手动启动时刻，P代表此发动机的位置编号。
        for (int i = 0; i < E; i++) {
            int T = scanner.nextInt();
            int P = scanner.nextInt();
            queue.add(new Integer[]{T,P});
        }
        Integer[] peek = queue.peek();
        temp[peek[1]] = peek[0];
        while(!queue.isEmpty()){
            Integer[] poll = queue.poll();
            int T = poll[0];
            int P = poll[1];
            // 计算左右点
            int left = P == 0 ? N-1:P-1;
            int right = P == N-1 ? 0:P+1;
            if (temp[left] == -1 || temp[left] > T + 1){
                temp[left] = T + 1;
                queue.add(new Integer[]{T + 1,left});
            }
            if (temp[right] == -1 || temp[right] > T + 1){
                temp[right] = T + 1;
                queue.add(new Integer[]{T + 1,right});
            }
        }
        System.out.println(Arrays.toString(temp));
        int max = 0;
        for (int i : temp) {
            max = Math.max(i,max);
        }
        int nums = 0;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] == max){
                nums++;
                ans.add(i);
            }
        }
        System.out.println(nums);
        System.out.println(ans);
    }
}
